Embodiments described herein relate generally to linked-node structures, and, in particular, to a linked-node structure configured to determine a range from a group of ranges including a key.
Determining a narrowest range of values including an input value from a group of ranges of values is often referred to as the range match problem. The range match problem is complicated by the fact that it involves at least two dimensions of analysis: the size of the ranges and the values included in the ranges. Thus, for each input value, it is necessary to determine which ranges from the group of ranges include the input value and which of those ranges is the most narrow. Neither ordering the ranges by size nor by beginning or ending value greatly simplifies the range matching problem. Common known solutions to the range matching problem involve brute force or exhaustive algorithms often implemented by many parallel range comparators.
One example of the range matching problem occurs in network switches, which often compare input values with a group of ranges to determine a best fit or most narrow range to properly route a data packet. The range matching problem can be particularly troublesome in such high-speed applications because the worst case behavior of known solutions imposes an upper limit on the number of data packets that can be processed per unit time. Although in many cases the worst case behavior is not observed, a network switch cannot be guaranteed to operate faster than the limit imposed by the worst case behavior of a given solution to the range matching problem. Thus, a need exists for improved methods and apparatus for improved worst case behavior of solutions to the range matching problem.